public class test {
    //leetcode 38.外观数列
    class Solution {
        public String countAndSay(int n) {
            String sb = "1";
            for (int i = 1; i < n; i++) {
                StringBuilder tmp = new StringBuilder();
                int len = sb.length();
                int left = 0;
                int right = 0;
                while (right < len) {
                    while(right < len && sb.charAt(left) == sb.charAt(right)) right++;
                    tmp.append(Integer.toString(right - left));
                    tmp.append(sb.charAt(left));
                    left = right;
                }
                sb = tmp.toString();
            }
            return sb;
        }
    }
    //leetcode 1419.数青蛙
    class Solution {
        // 1.哈希表做法(效率较低,由于元素数量极少,更推荐使用数组)
        public int minNumberOfFrogs(String croakOfFrogs) {
            HashMap<Character, Integer> map = new HashMap<>();
            // 存储可能出现的字符,对应标记下标
            char[] arrmap = { 'c', 'r', 'o', 'a', 'k' };
            int[] charToIndex = new int[128];
            charToIndex['c'] = 0;
            charToIndex['r'] = 1;
            charToIndex['o'] = 2;
            charToIndex['a'] = 3;
            charToIndex['k'] = 4;
            int len = croakOfFrogs.length();
            for (int i = 0; i < len; i++) {
                char c = croakOfFrogs.charAt(i);
                // 如果k处存在青蛙,使青蛙该回到c处重新蛙鸣
                if (c == 'c') {
                    int findk = map.getOrDefault('k', 0);
                    if (findk > 0) {
                        map.put('k', findk - 1);
                    }
                    map.put('c', map.getOrDefault('c', 0) + 1);
                } else {
                    int index = charToIndex[c];
                    char left = arrmap[index - 1];
                    if (map.getOrDefault(left, 0) <= 0) {
                        return -1;
                    } else {
                        map.put(left, map.get(left) - 1);
                        map.put(c, map.getOrDefault(c, 0) + 1);
                    }
                }
            }
            for (int i = 0; i < 4; i++) {
                if (map.getOrDefault(arrmap[i], 1) > 0) {
                    return -1;
                }
            }
            return map.get('k');
        }
        // 2.数组做法
        public int minNumberOfFrogs0(String croakOfFrogs) {
            int[] count = new int[5];
            int[] charToIndex = new int[128];
            charToIndex['c'] = 0;
            charToIndex['r'] = 1;
            charToIndex['o'] = 2;
            charToIndex['a'] = 3;
            charToIndex['k'] = 4;
            int maxFrogs = 0;
            int frogs = 0;
            for (char c : croakOfFrogs.toCharArray()) {
                if (c != 'c' && c != 'r' && c != 'o' && c != 'a' && c != 'k') {
                    return -1;
                }
                int index = charToIndex[c];
                if (index == 0) {
                    frogs++;
                    maxFrogs = Math.max(maxFrogs, frogs);
                } else {
                    if (count[index - 1] == 0) {
                        return -1;
                    }
                    count[index - 1]--;
                }
                count[index]++;
                if (index == 4) {
                    frogs--;
                    count[4]--;
                }
            }
            if (frogs != 0) {
                return -1;
            }
            return maxFrogs;
        }
    }
    //leetcode 215.数组中的第K个最大元素(基于快排的查找)
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            int num = qsort(nums,0,nums.length - 1,k);
            return num;
        }
        public int qsort(int[] nums,int l,int r,int k){
            if(l == r){
                return nums[l];
            }
            // 1.创建一个随机的基准元素
            int tmpindex = new Random().nextInt(r - l + 1) + l;
            int tmp = nums[tmpindex];
            int left = l - 1;
            int right = r + 1;
            int i = l;
            // 2.根据基准元素将数组分三块
            while(i < right){
                if(nums[i] < tmp){
                    swap(nums,++left,i++);
                }else if(nums[i] == tmp){
                    i++;
                }else {
                    swap(nums,--right,i);
                }
            }
            // 3.分类讨论
            // [l,left] [left+1,right-1] [right,r]
            int c = r - right + 1;
            int b = right - left - 1;
            if(c >= k){
                return qsort(nums,right,r,k);
            }else if(c + b >= k){
                return tmp;
            }else {
                return qsort(nums,l,left,k - b - c);
            }
        }
        public void swap(int[] arr,int i,int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}
